{
ID : phamnamlo2
PROB : psolve
LANG : PASCAL
}

program PSOLVE;
const
  fi = 'psolve.in';
  fo = 'psolve.out';
  max = 300;
  oo = 1000000000;
var
  d : array[0..2*max, 0..max] of longint;
  b, a, sb, sa : array[0..max] of longint;
  m, p, res : longint;

procedure inp;
var
  i : longint;
begin
  read(m, p);
  sb[0] := 0;
  sa[0] := 0;
  for i := 1 to p do
  begin
    read(b[i], a[i]);
    sb[i] := sb[i-1] + b[i];
    sa[i] := sa[i-1] + a[i];
  end;
end;

procedure init;
var
  i, j : longint;
begin
  for i := 1 to 2*p+1 do
    for j := 1 to p do d[i, j] := oo;
end;

procedure process;
var
  i, j, k : longint;
begin
  init;
  i := 2;
  while i <= 2*p+1 do
  begin
    for j := 1 to p do
    begin
      if d[i-1, j] < oo then d[i, j] := 0
      else
      for k := j-1 downto 0 do
      begin
        if (sb[j] - sb[k] > m) or (sa[j] - sa[k] > m) then break;
        if (d[i-1, k] + sb[j] - sb[k] <= m) then d[i, j] := sa[j] - sa[k];
      end;
    end;
    if d[i, p] = 0 then
    begin
      res := i;
      break;
    end;
    inc(i);
  end;
end;

procedure out;
begin
  writeln(res);
end;

begin
  assign(input, fi); reset(input);
  assign(output, fo); rewrite(output);

  inp;
  process;
  out;

  close(output);
  close(input);
end.
